class Solution
{
public:
    void reorderList(ListNode *head)
    {
        vector<ListNode *> nodes;
        ListNode *node = head;
        while (node != nullptr)
        {
            nodes.push_back(node);
            node = node->next;
        }
        int n = nodes.size();
        for (int i = 0; i < n / 2; ++i)
        {
            nodes[i]->next = nodes[n - i - 1];
            nodes[n - i - 1]->next = nodes[i + 1];
        }
        nodes[n / 2]->next = nullptr;
    }
};